Anti-aliasing scan conversion is used to generate a pixel image, defined on a rectangular array of pixels on a display device such as a Cathode Ray Tube (CRT) or a Light Emitting Diode (LED) display, from an original image (e.g., an image represented using geometric data (which may be specified by mathematical expressions) such as lines and curves describing the outlines of the image, which may be a line or a polygon, or the image of an alphanumeric character specified by a font). Since the pixel image is represented on a regularly spaced array of discrete points on the display device, the pixel image may have jagged edges, gross misrepresentation, or missing details. Many anti-aliasing scan conversion methods have been developed to efficiently generate the pixel image from the original image with minimum distortions or artifacts.
Anti-aliasing scan conversion typically averages a portion of the original image to determine the signal level (sometimes referred to as “coverage”) for a pixel. Since the scheme for averaging is generally the same for all the pixels, such methods for anti-aliasing scan conversion may be viewed as convolution of an image with a sampling kernel. The sampling kernel determines the weight for averaging at least a portion of the original image in determining the signal level for a pixel according to the position of the pixel.
FIG. 2 illustrates a method to anti-aliasing scan convert a one-dimensional signal using a convolution approach. Signal 201 represents the original signal, which is to be represented at the center points of the mesh formed by lines 211-219. For each of the sample points, a weight function, determined by a sampling kernel, is used to compute a weighted average of a neighboring portion of the original signal to produce a sampled signal level for the sample point. For example, weight function 222 weights the portion of signal 201 between lines 213 and 214 to produce sampled signal 241 for sample point 233. Since the weight function is non-zero for the portion of signal 201 between lines 213 and 214, signal level 241 is an average of this portion of signal 201 weighted according to the non-zero values in the corresponding portion of weight function. Similarly, weight functions 221-226 of the same form are used to compute weighted averages of signal 201 in generating sampled signal levels for points 232-237.
If the original signal is denoted as s(x) and the sampling kernel is denoted as f(x), the sampled signal p at point x can be expressed by the following convolution integral.
                              p          ⁡                      (            x            )                          =                              ∫                          -              ∞                                      +              ∞                                ⁢                                    s              ⁡                              (                u                )                                      ⁢                          f              ⁡                              (                                  u                  -                  x                                )                                      ⁢                                                  ⁢                          ⅆ              u                                                          (        1        )            
From the above convolution integral, it is seen that the weight function for the sample point at x=x0 is f(u−x0), which is specified by the sampling kernel f(x) according to the position of the sample point.
FIG. 3 illustrates a method to anti-aliasing scan convert an image using a two-dimensional convolution approach. Similar to the one-dimensional approach of FIG. 2, weight functions of the same form, determined by a sampling kernel, are used to compute the weighted averages of portions of the original image to obtain the sampled signal levels for all pixels. For example, signal 301 is sampled on a rectangular mesh of pixels. Weight function 303 is non-zero in the area between lines 323 and 324 (at x=x1 and x=x2 respectively) and lines 313 and 314 (at y=y1 and y=y2 respectively). Thus, the portion of signal 301 between lines 321 and 322 and between lines 311 and 312 is averaged with the weight according to weight function 303 to generate sampled signal level 305 for the pixel, which is between lines 325 and 326 and between lines 315 and 316. Weight functions in the same form of function 303 are used to obtain the weighted averages of signal 301 in producing the sampled signal levels for all the pixels on the mesh.
If the original signal of the image is denoted as s(x, y) and the sampling kernel is denoted as f(x, y), the sampled signal p at point (x, y) can be expressed by the following convolution integral.
                              p          ⁡                      (                          x              ,              y                        )                          =                              ∫                          -              ∞                                      +              ∞                                ⁢                                    ∫                              -                ∞                                            +                ∞                                      ⁢                                          s                ⁡                                  (                                      u                    ,                    v                                    )                                            ⁢                              f                ⁡                                  (                                                            u                      -                      x                                        ,                                          v                      -                      y                                                        )                                            ⁢                                                          ⁢                              ⅆ                u                            ⁢                              ⅆ                v                                                                        (        2        )            
Some anti-aliasing scan conversion methods use a closed form solution of the convolution integral; and the formula for the closed form solution is evaluated at every pixel position. Such approaches typically have best performance if the formula for the closed form solution is not complicated, but limit the choice of sampling kernels to those where the closed form solutions can be found. Some methods use kernels in the form of piecewise polynomials. Although closed form solutions can be found for the kernels in the form of piecewise polynomials, the closed form solutions typically are complicated with conditional operations. More details about using the kernels in the form of piecewise polynomials may be found in the article: “Polygon scan conversion by exact convolution”, by Tom Duff in Raster Imaging and Digital Typography, Proceedings of the International Conference, Cambridge University Press, 1989, pp. 154-168.
Some methods use supersampling at the locations of the pixels (e.g., point-sampling, stochastic sampling, or using a numerical integration method to compute weighted averages of values evaluated at discrete points in the areas of integration). A number of point-samples are collected from the signal to compute a weighted sum of these samples to generate the sampled signal level for a pixel. Such methods of supersampling are computationally expensive, as several evaluations per pixel are needed, but more flexible as only the weights need to be changed to accommodate different kernels.